Cross-correlation is a mathematical technique for measuring the similarity of two functions and is commonly used for searching a long signal to identify a shorter, known feature, such as when performing pattern recognition in radar signal analysis, neurophysiology, cryptanalysis, and economics. A cross-correlation is also referred to as a “sliding dot product” or “sliding inner product.”
Generally, a fast Fourier transform (FFT) and a pointwise product operation can be used to compute a cross-correlation of two discrete signals. The FFT takes as input two full vectors. For example, when computing the cross-correlation of signals a and b having length Na and Nb, respectively, these sequences can be respectively represented as full vectors of N elements: {a1, a2, . . . , aNa} and {b1, b2, . . . , bNb}. The fastest known algorithms for performing FFT-based cross-correlation have a computational complexity on the order of N log2 N.
In some applications, most of the elements in the sequence (e.g., {a1, a2, . . . , aNa}) are zero. Such signals are often referred to as being “sparse” and a sequence of length N having n non-zero elements can be referred to as having a “sparsity” of (N−n)/N, where the sparsity refers to the fraction of elements in the sequence that are zero.
For example, when operating a Geiger-mode laser radar, relatively long periods of time may elapse between detection events registered by the detector. As such, the output of such a detector will often contain long runs of zeroes and the sparsity of the data is often greater than 0.999.
Storing all of the elements (the “full vector”) in a sparse sequence can be space inefficient because of the number of duplicate elements (e.g., zero valued elements). In addition, because the FFT-based cross-correlation computation operates on the entire vector of N elements, there is a significant amount of wasted computational work in performing operations that result in a value of zero for most of the correlation coefficients.
Various alternative types of data structures are often used to represent sparse data using less space or memory. For example, a coordinate list data structure reduces space requirements by storing only the non-zero elements and the positions of those elements in the sequence.